package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">合并K个升序链表 [困难]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-23 10:17
 */
public class MergeKSortedLists_23 {

  public ListNode mergeKLists(ListNode[] lists) {
    return merge(lists, 0, lists.length - 1);
  }

  public ListNode merge(ListNode[] lists, int left, int right) {
    if (left == right) {
      return lists[left]; // 随便返回哪个都行
    }
    if (left > right) {
      return null;
    }
    int mid = (left + right) >> 1; // 每次递归之前将多个链表分成2份
    // 通过不断递归后最终出栈时只有2个链表，合并后再出栈还是合并两个链表不断递归到合并成完全有序
    return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
  }

  // 合并两个链表返回新的头结点
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
      return l2;
    }
    if (l2 == null) {
      return l1;
    }
    ListNode head = new ListNode(0);
    ListNode tail = head;
    // 循环遍历谁小就指向谁然后后移
    while (l1 != null && l2 != null) {
      if (l1.val <= l2.val) {
        tail.next = l1;
        l1 = l1.next;
      } else {
        tail.next = l2;
        l2 = l2.next;
      }
      tail = tail.next;
    }
    // 此时可能还有一端链表没有遍历完
    if (l1 == null) {
      tail.next = l2;
    }
    if (l2 == null) {
      tail.next = l1;
    }

    return head.next; // 第二个节点才是头结点
  }
}
